public class task2 {
    /*
    * 很久很久以前，有一位国王拥有5座金矿，每座金矿的黄金储量不同，需要参与挖掘的工人人数也不 同。
    * 例如有的金矿储量是500kg黄金，需要5个工人来挖掘；有的金矿储量是200kg黄金，需要3个工人 来挖掘……
    * 如果参与挖矿的工人的总数是10。每座金矿要么全挖，要么不挖，不能派出一半人挖取一半的金矿。
    * 要 求用程序求出，要想得到尽可能多的黄金，应该选择挖取哪几座金矿？
     * */

    public static void main(String[] args) {
        //
        int[] g = {400, 500, 200, 300, 350};
        int[] p = {5, 5, 3, 4, 3};
        System.out.println(getMostGold(5, 10, g, p));
    }

    /**
     *
     * @param n 第几个金矿
     * @param w 总共有几个人
     * @param g 数组，存放每个金矿的黄金数
     * @param p 数组，存放每个金矿需要的工人数
     * @return
     */
    public static int getMostGold(int n, int w, int[] g, int[] p) {

        int col = w + 1;   //因为F(x,0)也要用到，所以表格应该有w+1列
        int[] preResults = new int[col]; //存放上一行的结果
        int[] results = new int[col]; //存放当前行的结果

        //填充边界格子的值
        for(int i=0; i<=w; i++) {
            if(i < p[0]) {
                preResults[i] = 0;
            }else {
                preResults[i] = g[0];
            }
        }

        //填充其余格子的值，从上一行推出下一行，外层循环是金矿数量，内层循环是工人数
        for(int i=0; i<n; i++) {
            for(int j=0; j<col; j++) {
                if(j < p[i]) {
                    results[j] = preResults[j];
                }else {
                    results[j] = Math.max(preResults[j], preResults[j-p[i]] + g[i]);
                }
            }
            for(int j=0; j<col; j++) {
                preResults[j] = results[j];
            }
        }

        return results[w];
    }
}
